#include<stdio.h>
#include<stdlib.h>

// 二叉树代码实现02 https://www.bilibili.com/video/BV1Qx411m7jE


typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
} Node;

typedef struct{
    Node* root;
} Tree;

// 先序遍历
void preorder(Node *node){
    if (node != NULL)
    {
       printf("%d ", node->data);
       preorder(node->left);
       preorder(node->right);
    }
    
}

// 中序遍历
void inorder(Node *node){
    if (node != NULL)
    {
       inorder(node->left);
       printf("%d ", node->data);
       inorder(node->right);
    }
    
}

// 后序遍历
void afterorder(Node *node){
    if (node != NULL)
    {
       afterorder(node->left);
       afterorder(node->right);
       printf("%d ", node->data);
    }
    
}
// 二叉树值的插入
void insert(Tree* tree, int value){
    Node* node = malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    // 如果要插入的数本身就是空的，就放到根节点上
    if(tree->root == NULL){
        tree->root = node;
    }else{
        // 当前比较的节点
        Node* temp = tree->root;
        while (temp!= NULL)
        {
            // 若新节点比根值小，走左边
            if(value < temp->data){
                // 若左边的值为空，直接插入
                if(temp->left == NULL){
                    temp->left = node;
                    return;
                }
                // 若左边不为空，继续探测左边的值 
                temp = temp->left;
            }else{
                // 若新节点比根值大，走右边
                if(temp->right == NULL){
                    temp->right = node;
                    return;
                }
                temp = temp->right;
            }
        }
        

    }
}
// 求树的高度
// 思路：递归遍历左右树高度，得到哪个数最大即可返回
int getHeight(Node* node){
    if(node == NULL){
        return 0;
    }
    int left_h = getHeight(node->left);
    int right_h = getHeight(node->right);
    int max = left_h;
    if(right_h > max){
        max = right_h;
    }
    return max + 1;
}

int getMaximun(Node* node){
    if (node == NULL){
        return  -1;
    }
    int m1 = getMaximun(node->left);
    int m2 = getMaximun(node->right);
    int m3 = node->data;
    int max = m1;
    if(m2 > max){
        max = m2;
    }
    if(m3 > max){
        max = m3;
    }
    return max;
}

int main(){
    int arr[7] = {6, 3, 8, 2, 5, 1, 7};
    // int arr[2] = {6, 3};
    Tree tree;
    tree.root = NULL;

    int i;
    int size = sizeof(arr)/sizeof(arr[0]);
    for (i = 0; i < size; i++)
    {
        insert(&tree, arr[i]);
    }
    // 结论：二叉树的中序遍历，就是对该数的排序
    inorder(tree.root);
    printf("%s", "\n");

    // preorder(tree.root);
    // printf("%s", "\n");
    // afterorder(tree.root);

    printf("数的高度=%d\n", getHeight(tree.root));
    printf("树的最大值=%d\n", getMaximun(tree.root));
}